/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;
// node 
Node::Node(PageId pid) 
{
	this->pid = pid;
}
// getpid
PageId Node::getPid() 
{
	return this->pid;
}
// dll
DoubleLinkedList::DoubleLinkedList() 
{
	head = tail = 0;
	length = 0;
}

//insert
int DoubleLinkedList::insert(PageId pid) 
{
	if(length == 0) 
	{
		head = new Node(pid);
		tail = head;
		tail->next = 0;
		head->prev = 0;
		length == 1;
	} 
	else 
	{
		Node* temp = new Node(pid);
		tail->next = temp;
		temp->next = 0;
		temp->prev = tail;
		tail = temp;
		length++;
	}
	return 0;
}
// get data at tail
int DoubleLinkedList::getData(PageId& pid) 
{
	pid = tail->pid;
	Node* temp;
	if(tail->prev) 
	{
		temp = tail->prev;
	} 
	else 
	{
		return -1;
	}
	delete tail;
	tail = temp;
	return 0;
}
// destruct
int DoubleLinkedList::removeList() 
{
	while(head != tail) 
	{
		Node* temp = tail->prev;
		delete tail;
		tail = temp;
	}
	delete head;

	return 0;
}




/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{


	rootPid = -1;
	treeHeight = 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	RC rc = pf.open(indexname, mode);
	return rc;
    //return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{

	RC rc = pf.close();
	return rc;
//	return 0;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
    //return 0;
	IndexCursor cursor;
	PageId p;
	PageId oldPid;
	BTNonLeafNode sib;
	int midKey;
	BTNonLeafNode node;
	BTLeafNode leaf;
	

	if( locate(key, cursor) != 0) 
	{
	}


	if(treeHeight == 1) 
	{
		leaf.read(cursor.pid, pf);
		if( leaf.insert(key, rid) != 0) 
		{
			goto split;
		}
		leaf.write(cursor.pid, pf);
		return 0;
	}
	
	if( leaf.read(cursor.pid, pf) != 0) 
	{
	}


	if( leaf.insert(key, rid) != 0) 
	{
	split:
		BTLeafNode sibling;
		int siblingKey;
		leaf.insertAndSplit(key, rid, sibling, siblingKey);

		PageId nextNodePtr = leaf.getNextNodePtr();
		sibling.setNextNodePtr(nextNodePtr);
		leaf.setNextNodePtr(pf.endPid());

		if( leaf.write(cursor.pid, pf) != 0) 
		{
			return RC_FILE_WRITE_FAILED;
		}

		if( sibling.write(pf.endPid(), pf) != 0) 
		{
			return RC_FILE_WRITE_FAILED;
		}
	
		if(treeHeight == 1) 
		{
			BTNonLeafNode root;
			root.initializeRoot(cursor.pid, siblingKey, pf.endPid()-1);
			if(root.write(pf.endPid(), pf) != 0) 
			{
				return RC_FILE_WRITE_FAILED;
			}
			rootPid = pf.endPid() - 1;
			treeHeight++;
			return 0;
		}

		int i = 0;
		do 
		{
			oldPid = p;
			list.getData(p);

			if( node.read(p, pf) != 0) 
			{
				return RC_FILE_READ_FAILED;
			}

			if(i == 0) 
			{
	
				if(node.insert(siblingKey, pf.endPid()-1) == 0) 				{
					if( node.write(p, pf) != 0) 
					{
						return RC_FILE_WRITE_FAILED;
					}
					break;
				} 
				else 
				{
					node.insertAndSplit(siblingKey, cursor.pid, sib, midKey);
					sib.write(pf.endPid(), pf);
					if( node.write(p, pf) != 0) 
					{
						return RC_FILE_WRITE_FAILED;
					}
				}
			} 
			else 
			{

				if(node.insert(midKey, oldPid) == 0) 
				{
					if( node.write(p, pf) != 0) 
					{
						return RC_FILE_WRITE_FAILED;
					}
					break;
				} 
				else 
				{
					node.insertAndSplit(midKey, oldPid, sib, midKey);
					sib.write(pf.endPid(), pf);
					if(p == rootPid) 
					{
						BTNonLeafNode root;
						root.initializeRoot(p, midKey, pf.endPid()-1);
						if(root.write(pf.endPid(), pf) != 0) 
						{
							return RC_FILE_WRITE_FAILED;
						}
						rootPid = pf.endPid() - 1;
						treeHeight++;
					}
					if( node.write(p, pf) != 0) 
					{
						return RC_FILE_WRITE_FAILED;
					}
					break;
				}
			}
			i++;
		} while(p != rootPid);

		}
		if( leaf.write(cursor.pid, pf) != 0) 
		{
			return RC_FILE_WRITE_FAILED;
		}
	list.removeList();
	
	return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
//    return 0;
	int retval = 0;

	if(treeHeight == 0) 
	{
		cursor.pid = 1;
		cursor.eid = 0;
		treeHeight++;
		rootPid = 1;
	} 
	else if(treeHeight == 1) 
	{
		BTLeafNode root;
		int eid;
		if( root.read(rootPid, pf) != 0) 
		{
			return RC_FILE_READ_FAILED;
		}

		if( root.locate(searchKey, eid) != 0) 
		{
			return RC_NO_SUCH_RECORD;
		}
		cursor.pid = rootPid;
		cursor.eid = eid;
	} 
	else 
	{
		BTNonLeafNode node;
		if( node.read(rootPid, pf) != 0) 
		{
			return RC_FILE_READ_FAILED;
		}

		int level = 1;
		while(level < treeHeight) 
		{
			if(level == 1) 
			{
				list.insert(rootPid);
			} 
			else 
			{
				list.insert(nextPid);
			}

			if( node.locateChildPtr(searchKey, nextPid) != 0) 
			{
				return RC_NO_SUCH_RECORD;
			}


			if( node.read(nextPid, pf) != 0) 
			{
				return RC_FILE_READ_FAILED;
			}
			level++;
		}
		cursor.pid = nextPid;
		cursor.eid = 0;
	}

    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	
	BTLeafNode node;
	if(node.read(cursor.pid, pf) != 0) 
	{
		return RC_FILE_READ_FAILED;
	}

	if(node.readEntry(cursor.eid, key, rid) != 0) 
	{
		return RC_INVALID_RID;
	}

	if (cursor.eid < node.getKeyCount() - 1) 
	{
		cursor.eid++;
	} 
	else 
	{
		cursor.eid = 0;
		int next;
		next = node.getNextNodePtr();
		if(next == 0) 
		{
			return RC_END_OF_TREE;
		}
		cursor.pid = next;
	}	

    return 0;
}
